package class01

func MaxOneBorderSize(matrix [][]int) int {
	if len(matrix) < 1 {
		return 0
	}
	wid := len(matrix)
	mLen := len(matrix[0])
	leftOneRecord := make([][]int, wid)
	downOneRecord := make([][]int, wid)
	for i:=0; i<wid; i++ {
		leftOneRecord[i] = make([]int, mLen)
		downOneRecord[i] = make([]int, mLen)
	}
	SetMapBoarder(matrix, leftOneRecord, downOneRecord)
	for size := min(wid, mLen); size>=1; size-- {
		if HasSizeBoarder(matrix, leftOneRecord, downOneRecord, size) {
			return  size
		}
	}
	return 0
}

func HasSizeBoarder(matrix [][]int, leftOneRecord [][]int, downOneRecord [][]int, size int) bool {
	for i:=0; i<len(matrix); i++ {
		for j:=0; j<len(matrix[0]); j++ {
			if leftOneRecord[i][j] >= size && downOneRecord[i][j] >= size &&
				leftOneRecord[i+size-1][j] >= size && downOneRecord[i][j+size-1] >= size {
				return true
			}
		}
	}
	return false
}

func SetMapBoarder(matrix [][]int, leftOneRecord [][]int, downOneRecord [][]int){
	wid := len(matrix)
	mLen := len(matrix[0])

	for i:=0; i<wid; i++ {
		for j:=mLen-1; j>=0; j-- {
			if matrix[i][j] == 1 {
				leftOneRecord[i][j] += 1
				if j + 1 < mLen {
					leftOneRecord[i][j] += leftOneRecord[i][j+1]
				}
			}
		}
	}
	for i:=0; i<mLen; i++ {
		for j:=wid-1; j>=0; j-- {
			if matrix[j][i] == 1 {
				downOneRecord[j][i] += 1
				if j + 1 < wid {
					downOneRecord[j][i] += downOneRecord[j+1][i]
				}
			}
		}
	}
}